package nowcoder;

import java.util.ArrayList;

/**
 * @author wangxi03 created on 2021/5/7 2:37 下午
 * @version v1.0
 *
 * 获取最小k个数
 */
public class GetLeastNumbersSolution {

    public static void main(String[] args) {
        GetLeastNumbersSolution obj = new GetLeastNumbersSolution();
        int[] arr = {4,5,1,6,2,7,3,8};
        ArrayList<Integer> res = obj.getLeastNumbers_Solution(arr, 8);


    }

    public ArrayList<Integer> getLeastNumbers_Solution(int [] input, int k) {
        ArrayList<Integer> res = new ArrayList<>();
        if (input == null || input.length <= 0 || k > input.length) {
            return res;
        }
        sort(input, 0, input.length - 1, res, k);
        return res;
    }

    private void sort(int[] arr, int start, int end, ArrayList<Integer> res, int k) {
        // 边界情况，因此这里不能带等号
        if (start > end) {
            return;
        }
        int index = partition(arr, start, end);
        if (index == k - 1) {
            for (int i = 0; i < k; i++) {
                res.add(arr[i]);
            }
            return;
        } else if (index > k - 1) {
            // 这里的end需要改下
            sort(arr, start, index - 1, res, k);
        } else {
            sort(arr, index + 1, end, res, k);
        }
    }
    private int partition(int[] arr, int start, int end) {
        int key = arr[start];
        while (start < end) {
            while (start < end && arr[end] >= key) {
                end--;
            }
            arr[start] = arr[end];
            while (start < end && arr[start] <= key) {
                start++;
            }
            arr[end] = arr[start];
        }
        arr[end] = key;
        return end;
    }
}
